1. Field of the Invention
The present invention relates to a system and a method for constructing peer-to-peer overlay graphs in a network environment.
2. Description of Background Art
The mapping of network architectures is a well studied field. Efficiently building and maintaining resilient overlay networks is important for many applications. As used herein resilient networks can be considered as networks that operate even in the presence of faults either through tolerance of faults or through some repair techniques in the presence of faults. Additionally, an overlay network is a virtual network of nodes and links built on top of an already existing network. The overlay may also provide some additional services that are not provided by the underlying network. Such overlay networks should be easy to build and maintain in the presence of overlay node additions and deletions. They also should have high resilience, low latency and bounded resource usage at any node. The graphs modeling these overlay networks should also be highly connected, have low diameter, and bounded degree at each node. Regular graphs exhibit several of these desired properties and have been investigated for efficient overlay design. Typically, algorithms use offline techniques to build regular graphs with strict bounds on resilience and such techniques are not designed to maintain these properties in the presence of online additions, deletions and failures. On the other hand, random regular graphs are easy to construct and maintain, and provide good properties without strict guarantees.
The generation of random graphs with a given degree sequence is a method attributed to Molloy and Reed. The method is general and does not necessarily produce a connected graph. Such graphs can be then connected but the computational burden of this correction is substantial.
Regular graphs, i.e., graphs with a fixed degree at each node, have been studied as candidates for overlay design (see, e.g., R. Melamed and I. Keidar, “Araneola: A Scalable Reliable Multicast System for Dynamic Environment”, 3rd IEEE International Symposium on Network Computing and Applications (IEEE NCA), pages 5-14, September 2004, and G. Pandurangan, P. Raghavan, and E. Upfal, “Building Low-Diameter Peer-to-Peer Networks”, IEEE Journal on Selected Areas in Communications, 21(6):995-1002, August 2003). A number of algorithms presented in literature use offline techniques to construct regular graphs with guaranteed bounds on resilience (see, e.g., X. Hou and T. Wang, “On Generalized k-Diameter of k-Regular k-Connected Graphs”, Taiwanese Journal of Mathematics, 8(4):739-745, December 2004, and X. Hou and T. Wang, “An Algorithm to Construct k-Regular k Connected Graphs with Maximum k-Diameter”, Graphs and Combinatorics, 19:111-119, 2003). However, these techniques have to be necessarily offline due to the large number of computations required to explore the solution space and provide strict bounds on the resilience. These techniques are not designed to maintain the required properties in the presence of joins, leaves and failures of the overlay nodes.
Randomized algorithms can be effectively used to solve problems very efficiently while providing good guarantees either in the average case, or with provably high probability. Random graphs can be built without any global knowledge and hence are good candidates for distributed design. In particular, Pandurangan et al. present a randomized graph building scheme for low diameter peer-to-peer networks with a bounded degree (see, G. Pandurangan, P. Raghavan, and E. Upfal, “Building Low-Diameter Peer-to-Peer Networks”, IEEE Journal on Selected Areas in Communications, 21(6):995-1002, August 2003). However, their scheme focuses on building low-diameter connected graphs and not on guarantees on the resilience of the resulting network to node and edge failures. Further, the method proposed by Pandurangan et al. requires a central server.
Random regular graphs are fixed degree graphs built using a randomized approach, and as such can be constructed in a distributed way, although the graphs may not necessarily be selected with equal probabilities. These graphs of degree d have interesting properties like d-connectedness not in the worst case but with a very high probability. As an example, the Araneola multicast overlays, noted above, are built using random regular graphs and rely on the connectedness and low diameter properties of random regular graphs to ensure that their multicast overlay is resilient with a high probability. There are, however, no strict guarantees on the resilience of such graphs.